package com.ryujung.binary_tree.leetCode_124;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {

    int sumMax = Integer.MIN_VALUE;

    /**
     * 思路：
     * 使用递归方式
     * 类似DFS深度优先算法，每个节点需要遍历所有的子树，并获得最大值
     * 不一定过root节点，那么可能有两种情况，
     * 一种是left-root-right 是最大值，抛弃root的父节点，无法递归
     * 另一种是root-max(left,right)-root的父节点，可以进行递归
     * 所以需要以递归计算第二种方式的最大值
     * 同时记录第一种方式的最大值
     * <p>
     * 注意：极端情况，如果二叉树均为负数，那么最大路径就是 空树，max=0
     * 所以当递归遇到max<0时，应该取0值，即舍弃当前递归的子树
     * <p>
     * 左右子树都要自底向上进行计算
     * 所以大框架选择后续遍历：左子树、右子树、根节点。
     */
    public int maxPathSum(TreeNode root) {
        int max1 = maxPathSumHelper(root);
        return Math.max(max1, sumMax);
    }

    public int maxPathSumHelper(TreeNode root) {
        if (root == null) return 0;

        // max小于0时，应该取0值，即舍弃当前子树
        int left = Math.max(0, maxPathSumHelper(root.left));
        int right = Math.max(0, maxPathSumHelper(root.right));

        // 两种情况： 一，当前子树值最大。二、root+max（left，right）最大
        sumMax = Math.max(sumMax, root.val + left + right);  // 更新最大子树的值
        int max2 = root.val + Math.max(left, right);

        // 两种方式中，只有一种可以进行递归，所以只能返回max2
        // 那么，如何传递max1的值? 设置全局变量
        return max2;
        // 结果需要返回max2和max1的最大值，所以要将以上代码递归代码封装成helper方法
    }
}